package LeetCode;

import java.util.ArrayList;
import java.util.List;

public class LC_046_2_Permutations {
    public static void main(String[] args) {

    }

    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        permute_recur(nums, 0, nums.length - 1);
        return res;
    }

    private void permute_recur(int[] nums, int start, int end) {
        if (start == end) {
            List<Integer> list = new ArrayList<>();
            for (int num : nums)
                list.add(num);
            res.add(list);
        } else {
            for (int i = start; i <= end; i++) {
                swap(nums, i, start);
                permute_recur(nums, start + 1, end);
                swap(nums, i, start);
            }
        }
    }

    private void swap(int[] nums, int l, int r) {
        if (l == r)
            return;
        nums[l] = nums[l] ^ nums[r];
        nums[r] = nums[l] ^ nums[r];
        nums[l] = nums[l] ^ nums[r];
    }
}
